Search Results

Documents authored by Newman, Ilan

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.98
Strongly Sublinear Algorithms for Testing Pattern Freeness

Authors: Ilan Newman and Nithin Varma

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
For a permutation π:[k] → [k], a function f:[n] → ℝ contains a π-appearance if there exists 1 ≤ i₁ < i₂ < … < i_k ≤ n such that for all s,t ∈ [k], f(i_s) < f(i_t) if and only if π(s) < π(t). The function is π-free if it has no π-appearances. In this paper, we investigate the problem of testing whether an input function f is π-free or whether f differs on at least ε n values from every π-free function. This is a generalization of the well-studied monotonicity testing and was first studied by Newman, Rabinovich, Rajendraprasad and Sohler [Ilan Newman et al., 2019]. We show that for all constants k ∈ ℕ, ε ∈ (0,1), and permutation π:[k] → [k], there is a one-sided error ε-testing algorithm for π-freeness of functions f:[n] → ℝ that makes Õ(n^o(1)) queries. We improve significantly upon the previous best upper bound O(n^{1 - 1/(k-1)}) by Ben-Eliezer and Canonne [Omri Ben-Eliezer and Clément L. Canonne, 2018]. Our algorithm is adaptive, while the earlier best upper bound is known to be tight for nonadaptive algorithms.
Cite as

Ilan Newman and Nithin Varma. Strongly Sublinear Algorithms for Testing Pattern Freeness. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 98:1-98:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{newman_et_al:LIPIcs.ICALP.2022.98,
  author =	{Newman, Ilan and Varma, Nithin},
  title =	{{Strongly Sublinear Algorithms for Testing Pattern Freeness}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{98:1--98:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.98},
  URN =		{urn:nbn:de:0030-drops-164390},
  doi =		{10.4230/LIPIcs.ICALP.2022.98},
  annote =	{Keywords: Property testing, Pattern freeness, Sublinear algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.100
New Sublinear Algorithms and Lower Bounds for LIS Estimation

Authors: Ilan Newman and Nithin Varma

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Estimating the length of the longest increasing subsequence (LIS) in an array is a problem of fundamental importance. Despite the significance of the LIS estimation problem and the amount of attention it has received, there are important aspects of the problem that are not yet fully understood. There are no better lower bounds for LIS estimation than the obvious bounds implied by testing monotonicity (for adaptive or nonadaptive algorithms). In this paper, we give the first nontrivial lower bound on the complexity of LIS estimation, and also provide novel algorithms that complement our lower bound. Specifically, we show that for every ε ∈ (0,1), every nonadaptive algorithm that outputs an estimate of the LIS length in an array of length n to within an additive error of ε n has to make log^{Ω(log (1/ε))} n queries. Next, we design nonadaptive LIS estimation algorithms whose complexity decreases as the number of distinct values, r, in the array decreases. We first present a simple algorithm that makes Õ(r/ε³) queries and approximates the LIS length with an additive error bounded by ε n. This algorithm has better complexity than the best previously known adaptive algorithm (Saks and Seshadhri; 2017) for the same problem when r ≪ polylog (n). We use our algorithm to construct a nonadaptive algorithm with query complexity Õ(√r⋅ poly(1/λ)) that, when the LIS is of length at least λ n, outputs a multiplicative Ω(λ)-approximation to the LIS length. Our algorithm improves upon the state of the art nonadaptive LIS estimation algorithm (Rubinstein, Seddighin, Song, and Sun; 2019) in terms of the approximation guarantee. Finally, we present a O(log n)-query nonadaptive erasure-resilient tester for monotonicity. Our result implies that lower bounds on erasure-resilient testing of monotonicity does not give good lower bounds for LIS estimation. It also implies that nonadaptive tolerant testing is strictly harder than nonadaptive erasure-resilient testing for the natural property of monotonicity.
Cite as

Ilan Newman and Nithin Varma. New Sublinear Algorithms and Lower Bounds for LIS Estimation. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 100:1-100:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{newman_et_al:LIPIcs.ICALP.2021.100,
  author =	{Newman, Ilan and Varma, Nithin},
  title =	{{New Sublinear Algorithms and Lower Bounds for LIS Estimation}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{100:1--100:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.100},
  URN =		{urn:nbn:de:0030-drops-141699},
  doi =		{10.4230/LIPIcs.ICALP.2021.100},
  annote =	{Keywords: longest increasing subsequence, monotonicity, distance estimation, sublinear algorithms}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.32
Online Embedding of Metrics

Authors: Ilan Newman and Yuri Rabinovich

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We study deterministic online embeddings of metric spaces into normed spaces of various dimensions and into trees. We establish some upper and lower bounds on the distortion of such embedding, and pose some challenging open questions.
Cite as

Ilan Newman and Yuri Rabinovich. Online Embedding of Metrics. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{newman_et_al:LIPIcs.SWAT.2020.32,
  author =	{Newman, Ilan and Rabinovich, Yuri},
  title =	{{Online Embedding of Metrics}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{32:1--32:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.32},
  URN =		{urn:nbn:de:0030-drops-122792},
  doi =		{10.4230/LIPIcs.SWAT.2020.32},
  annote =	{Keywords: Metric spaces, online embedding}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.21
Every Property of Outerplanar Graphs is Testable

Authors: Jasine Babu, Areej Khoury, and Ilan Newman

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
A D-disc around a vertex v of a graph G=(V,E) is the subgraph induced by all vertices of distance at most D from v. We show that the structure of an outerplanar graph on n vertices is determined, up to modification (insertion or deletion) of at most epsilon n edges, by a set of D-discs around the vertices, for D=D(epsilon) that is independent of the size of the graph. Such a result was already known for planar graphs (and any hyperfinite graph class), in the limited case of bounded degree graphs (that is, their maximum degree is bounded by some fixed constant, independent of |V|). We prove this result with no assumption on the degree of the graph. A pure combinatorial consequence of this result is that two outerplanar graphs that share the same local views are close to be isomorphic. We also obtain the following property testing results in the sparse graph model: * graph isomorphism is testable for outerplanar graphs by poly(log n) queries. * every graph property is testable for outerplanar graphs by poly(log n) queries. We note that we can replace outerplanar graphs by a slightly more general family of k-edge-outerplanar graphs. The only previous general testing results, as above, where known for forests (Kusumoto and Yoshida), and for some power-law graphs that are extremely close to be bounded degree hyperfinite (by Ito).
Cite as

Jasine Babu, Areej Khoury, and Ilan Newman. Every Property of Outerplanar Graphs is Testable. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{babu_et_al:LIPIcs.APPROX-RANDOM.2016.21,
  author =	{Babu, Jasine and Khoury, Areej and Newman, Ilan},
  title =	{{Every Property of Outerplanar Graphs is Testable}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.21},
  URN =		{urn:nbn:de:0030-drops-66448},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.21},
  annote =	{Keywords: Property testing, Isomorphism, Outerplanar graphs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact